package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code90LongestValidParentheses {

    public int longestValidParentheses(String s) {
        char[] str = s.toCharArray();
        int n = str.length;
        int max = 0;
        // 记录左右括号数量
        int lCount = 0;
        int rCount = 0;
        for (char c : str) {
            if (c == '(') {
                lCount++;
            } else {
                rCount++;
            }
            if (lCount == rCount) {
                // 记录有效括号最大长度
                max = Math.max(max, 2 * lCount);
            } else if (rCount > lCount) {
                // 指定无效了，重新开始
                lCount = 0;
                rCount = 0;
            }
        }
        lCount = rCount = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                lCount++;
            } else {
                rCount++;
            }
            if (lCount == rCount) {
                max = Math.max(max, 2 * rCount);
            } else if (lCount > rCount) {
                lCount = rCount = 0;
            }
        }
        return max;
    }

    public int longestValidParentheses1(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        char[] str = s.toCharArray();
        int n = str.length;
        int i = n - 1;
        while (i >= 0 && str[i] == '(') {
            i--;
        }
        if (i < 0) {
            return 0;
        }
//        int[] max = new int[1];
//        process(str, i, max);
//        return max[0];

        int max = 0;
        int[] dp = new int[n];
        dp[0] = 0;
        for (int j = 1; j < n; j++) {
            if (str[j] != ')') {
                continue;
            }
            int preLen = dp[j - 1];
            int preIndex = j - preLen - 1;
            if (preIndex >= 0 && str[preIndex] == '(') {
                dp[j] = preLen + 2;
                if (preIndex > 0) {
                    dp[j] += dp[preIndex - 1];
                }
                max = Math.max(max, dp[j]);
            }
        }
        return max;
    }

    public int process(char[] str, int index, int[] max) {
        // 以 index 位置结尾是否有效
        if (index == 0) {
            return 0;
        }
        if (index == 1) {
            int curLen = str[0] == '(' && str[1] == ')' ? 2 : 0;
            max[0] = Math.max(max[0], curLen);
            return curLen;
        }
        // index 位置是 ) 考察前面有效长度的更前一位是否是 (
        if (str[index] == ')') {
            int preLen = process(str, index - 1, max);
            int preIndex = index - preLen - 1;
            if (preIndex >= 0 && str[preIndex] == '(') {
                int curLen = preLen + 2;
                // 可能还有
                if (preIndex > 0) {
                    curLen += process(str, preIndex - 1, max);
                }
                max[0] = Math.max(max[0], curLen);
                return curLen;
            }
        } else {
            process(str, index - 1, max);
        }
        return 0;
    }
}
